<?php
/**
 * Created by PhpStorm.
 * User: admin
 * Date: 2019/1/10
 * Time: 10:23
 */

/**
 * 使用循环实现
 * @param $findDate
 * @param $searchVal
 * @return int
 */
function binarySearch($findDate, $searchVal)
{
    $count = count($findDate);
    if($count<1){
        return -1;
    }
    $low = 0;
    $high = $count - 1;
    while ($high >= $low){
        $mid = (int)(($low+$high)/2);
        if ($findDate[$mid] == $searchVal){
            return $mid;
        }
        if($findDate[$mid] > $searchVal){
            $high = $mid-1;
        }
        if($findDate[$mid] < $searchVal){
            $low = $mid+1;
        }
    }
    return -1;
}

/**
 * 递归实现
 * 终止条件：找到了值，或者low>high
 */
function binarySearchInternally($searchDate, $searchVal, $low, $high)
{
    if($low>$high){
        return -1;
    }

    $mid = (int)(($low + $high)/2);

    if($searchDate[$mid] == $searchVal){
        return $mid;
    }

    if($searchDate[$mid] > $searchVal){
        $high = $mid-1;
        return binarySearchInternally($searchDate, $searchVal, $low, $high);
    }

    if($searchDate[$mid] < $searchVal){
        $low = $mid+1;
        return binarySearchInternally($searchDate, $searchVal, $low, $high);
    }


}


$findData = [1, 2,3, 4, 6, 8, 9, 11];
$red = binarySearch($findData, 5);
echo $red.PHP_EOL;
$red = binarySearch($findData, 6);
echo $red.PHP_EOL;

echo "---------".PHP_EOL;
$red = binarySearchInternally($findData, 5,0 ,7);
echo $red.PHP_EOL;
$red = binarySearchInternally($findData, 6,0 ,7);
echo $red.PHP_EOL;